#include <iostream>
#include <stack>
#include <vector>

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for(int i = 0;i<height.size();++i)
        {
            //int top = 0;
            while(!st.empty()&&height[i]>height[st.top()])
            {
                int top = st.top();
                st.pop();
                if(st.empty())
                {
                    break;
                }
                int left = st.top();
                int wid = i-left-1;
                int hei = min(height[left],height[i])-height[top];
                ans+=(wid*hei);
            }
            st.push(i);
            
        }
        return ans;
    }
};

